2 keys keyboard

Time: O(sqrt(N)); Space: O(1); medium

Initially on a notepad only one character ‘A’ is present. You can perform two operations on this notepad for each step:

Copy All: You can copy all the characters present on the notepad (partial copy is not allowed). Paste: You can paste the characters which are copied last time.

Given a number n. You have to get exactly n ‘A’ on the notepad by performing the minimum number of steps permitted. Output the minimum number of steps to get n ‘A’.

Example 1:

Input: n = 3

Output: 3

Explanation:

  • Intitally, we have one character ‘A’.

  • In step 1, we use Copy All operation.

  • In step 2, we use Paste operation to get ‘AA’.

  • In step 3, we use Paste operation to get ‘AAA’.

Constraints:

  • The n will be in the range [1, 1000]

Hints:

  1. How many characters may be there in the clipboard at the last step if n = 3? n = 7? n = 10? n = 24?

[3]:

class Solution1(object):
    """
    Time: O(SQRT(N))
    Space: O(1)
    """
    def minSteps(self, n):
        """
        :type n: int
        :rtype: int
        """
        result = 0
        p = 2

        # the answer is the sum of prime factors
        while p**2 <= n:
            while n % p == 0:
                result += p
                n //= p
            p += 1
        if n > 1:
            result += n

        return result

[4]:

s = Solution1()

n = 3
assert s.minSteps(n) == 3